The present invention generally relates to a method for applying and deciding between several alternative optimizations to a design and the selection of the preferred alternative being determined by an evaluator which compares the results of the different optimization alternatives and more particularly relates to the application of the method to electronic design automation.
In deep sub-micron integrated circuit design, design domains such as logic synthesis and placement which have traditionally been optimized separately are interacting to such an extent that independent considerations of these domains is no longer possible. In addition to traditional design metrics such as area (e.g., placement and wiring, floor planning and the like) and timing, there are also new issues which affect the functionality and/or optimality of designs such as noise, electromigration and power.
All of these trends require much tighter integration of design and analysis tools from different domains than has been seen in the past. This in turn requires that design analysis and optimization tools operate incrementally. Despite this need for the tools to be integrated and incremental, they must remain modular and separable to manage the complexity of the design system, to restrict the expertise needed to develop tools for particular design domains, and to allow for replacement of tools in different domains as better techniques become available.
Timing analysis is a well-known tool. Timing analysis can be in late mode (making sure signals get where they need to on time) or early mode (making sure signals are held at a stable state long enough). Timing generally refers to late mode unless early mode is specifically stated. Late mode arrival time is the latest time that a signal arrives (i.e., becomes stable) at some point. Late mode required arrival time is the time a signal needs to arrive at some point in order to meet all timing requirements. Late mode slack is required arrival time minus arrival time. Early mode arrival time is the earliest a signal will become unstable at some point. Early mode required arrival time is the latest time that a signal needs to be held stable at some point in order to meet all timing requirements. Early mode slack is arrival time minus required arrival time. In both cases, slack is defined so that a negative slack value indicates a timing problem.
Abato et al. U.S. Pat. No. 5,508,937, the disclosure of which is incorporated by reference herein, discloses an incremental timing analyzer which produces slack values at any circuit pin in the design.
Hathaway U.S. Pat. No. 5,740,067, the disclosure of which is incorporated by reference herein, discloses an incremental analyzer which computes the total skew cost for a clock tree.
For efficiency, incremental analysis tools should employ lazy evaluation. This means that no analysis or reanalysis is done until requested. Thus, instead of doing a lot of computation up front, the computation is done only when the information is needed. When computing an updated value an analyzer may employ incomplete lazy evaluation if it can determine that only a subset of pending changes can affect the requested value.
All of these concerns require a different tool integration architecture than has been used in the past; such an architecture defines the manner in which the various analysis and optimization tools interact and is the subject of the present invention.
An important purpose of the present invention in modularizing incremental design tools is to separate design modification tools from the tools which analyze the results of those modifications. Such separation provides the following benefits:
It allows use of a single design optimization tool in different contexts with different cost functions and considerations;
Within one stage of design (e.g., post-placement) it allows use of the same evaluation functions for many different design optimizations, ensuring consistency in the objectives during that stage; and
It allows evaluation of a series of optimizations performed by different independent design tools, e.g., buffer insertion and buffer placement. This is important if each of these separate optimizations is not complete in and of itself, since an incomplete optimization cannot be meaningfully evaluated.
One aspect of the invention relates to a method for analyzing and optimizing a design, the method comprising the steps of:
(a) providing a model representing a design being optimized;
(b) providing a checkpoint manager for recording changes of the design between selected reference points, the selected reference points being an initial checkpoint and a final checkpoint;
(c) providing an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(d) applying a first optimization procedure to cause at least one change in the design; and
(e) evaluating the at least one design change to determine the net cost and benefit of the change, wherein if the at least one design change results in improved net cost and benefit, then the design is optimized.
A second aspect of the invention relates to a method for analyzing and optimizing a design, the method comprising the steps of:
(a) providing a model representing a design being optimized;
(b) providing a checkpoint manager for recording changes of the design between selected reference points, the selected reference points being an initial checkpoint and a final checkpoint;
(c) providing an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(d) establishing an initial checkpoint;
(e) applying an optimization procedure to cause at least one change in the design from the initial checkpoint to a second checkpoint;
(f) evaluating the at least one design change resulting from the optimization procedure to determine the net cost and benefit of the change;
(g) returning the design model to the initial checkpoint;
(h) repeating steps (d), (e) and (f);
(i) comparing the net cost and benefit of the optimization procedure just performed with the best net cost and benefit of any previous optimization procedure performed to result in a best net cost and benefit of the optimization procedures performed thus far, and retaining the best net cost and benefit of the optimization procedures performed thus far;
(j) returning the design model to the initial checkpoint;
(k) repeating steps (g), (h) and (i) a predetermined number of times; and
(l) returning the design model to its state at the checkpoint of the optimization procedure that has resulted in the best net cost and benefit or to its state at the initial checkpoint in the event that no optimization procedure improved the design model so that the design is optimally changed to a new design.
A third aspect of the invention relates to a method for analyzing and optimizing a design, the method comprising the steps of:
(a) providing a model representing a design being optimized;
(b) providing a checkpoint manager for recording changes of the design between selected checkpoint reference points;
(c) providing an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(d) establishing and retaining a checkpoint;
(e) applying an optimization procedure to cause at least one change in the design from the previously retained checkpoint to a final checkpoint;
(f) evaluating the at least one design change resulting from the optimization procedure to determine the net cost and benefit of the change;
(g) comparing the net cost and benefit of the optimization procedure just performed with the net cost and benefit of the previous optimization procedure performed associated with the previous retained checkpoint, and retaining the best net cost and benefit and final checkpoint of the optimization procedure just performed if there is an improved net cost and benefit;
(h) returning the design model to the immediately previous retained checkpoint;
(i) repeating steps (e) to (h) a predetermined number of times; and
(j) returning the design model to its state at the checkpoint of the optimization procedure that has resulted in the last net cost and benefit retained or to its state at the initial checkpoint in the event that no optimization procedure improved the design model so that the design is optimally changed to a new design.
A fourth aspect of the invention relates to a computer program product comprising:
(a) a computer usable medium having computer readable program code means embodied therein for causing a design to be analyzed and optimized, the computer readable program code means in the computer program product comprising:
(b) computer readable program code means for causing a computer to effect a model representing a design being optimized;
(c) computer readable program code means for causing a computer to effect a checkpoint manager for recording changes of the design between selected reference points, the selected reference points being an initial checkpoint and a final checkpoint;
(d) computer readable program code means for causing a computer to effect an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(e) computer readable program code means for causing a computer to effect the application of a first optimization procedure to cause at least one change in the design; and
(f) computer readable program code means for causing a computer to effect the evaluation of the at least one design change to determine the net cost and benefit of the change, wherein if the at least one design change results in improved net cost and benefit, then the design is optimized.
A fifth aspect of the invention relates to a computer program product comprising:
(a) a computer usable medium having computer readable program code means embodied therein for causing a design to be analyzed and optimized, the computer readable program code means in the computer program product comprising:
(b) computer readable program code means for causing a computer to effect a model representing a design being optimized;
(c) computer readable program code means for causing a computer to effect a checkpoint manager for recording changes of the design between selected reference points, the selected reference points being an initial checkpoint and a final checkpoint;
(d) computer readable program code means for causing a computer to effect an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(e) computer readable program code means for causing a computer to effect the establishment of an initial checkpoint;
(f) computer readable program code means for causing a computer to effect the application of a first optimization procedure to cause at least one change in the design from the initial checkpoint to a second checkpoint;
(g) computer readable program code means for causing a computer to effect the evaluating the at least one design change resulting from the optimization procedure to determine the net cost and benefit of the change;
(h) computer readable program code means for causing a computer to effect the return of the design model to the initial checkpoint;
(i) computer readable program code means for causing a computer to effect the repetition of (e), (f) and (g);
(j) computer readable program code means for causing a computer to effect the comparison of the net cost and benefit of the optimization procedure just performed with the best net cost and benefit of any previous optimization procedure performed to result in a best net cost and benefit of the optimization procedures performed thus far, and the retention of the best net cost and benefit of the optimization procedures performed thus far;
(k) computer readable program code means for causing a computer to effect the return of the design model to the initial checkpoint;
(l) computer readable program code means for causing a computer to effect the repetition of (h), (i) and (k) a predetermined number of times; and
(m) computer readable program code means for causing a computer to effect the returning of the design model to its state at the checkpoint of the optimization procedure that has resulted in the best net cost and benefit or to its state at the initial checkpoint in the event that no optimization procedure improved the design model so that the design is optimally changed to a new design.
A sixth aspect of the invention relates to a computer program product comprising:
(a) a computer usable medium having computer readable program code means embodied therein for causing a design to be analyzed and optimized, the computer readable program code means in the computer program product comprising:
(b) computer readable program code means for causing a computer to effect a model representing a design being optimized;
(c) computer readable program code means for causing a computer to effect a checkpoint manager for recording changes of the design between selected reference points;
(d) computer readable program code means for causing a computer to effect an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(e) computer readable program code means for causing a computer to effect the establishment and retention of a checkpoint;
(f) computer readable program code means for causing a computer to effect the application of an optimization procedure to cause at least one change in the design from the previously retained checkpoint to a final checkpoint;
(g) computer readable program code means for causing a computer to effect the evaluation of the at least one design change resulting from the optimization procedure to determine the net cost and benefit of the change;
(h) computer readable program code means for causing a computer to effect the comparison of the net cost and benefit of the optimization procedure just performed with the net cost and benefit of the previous optimization procedure performed associated with the previous retained checkpoint, and the retention of the best net cost and benefit and final checkpoint of the optimization procedure just performed if there is an improved net cost and benefit;
(i) computer readable program code means for causing a computer to effect the return of the design model to the immediately previous retained checkpoint;
(j) computer readable program code means for causing a computer to effect the repetition of (f) to (i) a predetermined number of times; and
(k) computer readable program code means for causing a computer to effect the returning of the design model to its state at the checkpoint of the optimization procedure that has resulted in the last net cost and benefit retained or to its state at the initial checkpoint in the event that no optimization procedure improved the design model so that the design is optimally changed to a new design.
A seventh aspect of the invention relates to a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for analyzing and optimizing a design, the method steps comprising the steps of:
(a) providing a model representing a design being optimized;
(b) providing a checkpoint manager for recording changes of the design between selected reference points, the selected reference points being an initial checkpoint and a final checkpoint;
(c) providing an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(d) applying a first optimization procedure to cause at least one change in the design; and
(e) evaluating the at least one design change to determine the net cost and benefit of the change, thereby determining if the design change will result in an optimized design.
An eighth aspect of the invention relates to a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for analyzing and optimizing a design, the method steps comprising the steps of:
(a) providing a model representing a design being optimized;
(b) providing a checkpoint manager for recording changes of the design between selected reference points, the selected reference points being an initial checkpoint and a final checkpoint;
(c) providing an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(d) establishing an initial checkpoint;
(e) applying an optimization procedure to cause at least one change in the design from the initial checkpoint to a second checkpoint;
(f) evaluating the at least one design change resulting from the optimization procedure to determine the net cost and benefit of the change;
(g) returning the design model to the initial checkpoint;
(h) repeating steps (d), (e) and (f);
(i) comparing the net cost and benefit of the optimization procedure just performed with the best net cost and benefit of any previous optimization procedure performed to result in a best net cost and benefit of the optimization procedures performed thus far, and retaining the best net cost and benefit of the optimization procedures performed thus far;
(j) returning the design model to the initial checkpoint;
(k) repeating steps (g), (h) and (i) a predetermined number of times; and
(l) returning the design model to its state at the checkpoint of the optimization procedure that has resulted in the best net cost and benefit or to its state at the initial checkpoint in the event that no optimization procedure improved the design model so that the design is optimally changed to a new design.
A ninth aspect of the invention relates to a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for analyzing and optimizing a design, a method for analyzing and optimizing a design, the method steps comprising the steps of:
(a) providing a model representing a design being optimized;
(b) providing a checkpoint manager for recording changes of the design between selected checkpoint reference points;
(c) providing an evaluator for determining the net cost and benefit of the changes between the selected reference points;
(d) establishing and retaining a checkpoint;
(e) applying an optimization procedure to cause at least one change in the design from the previously retained checkpoint to a final checkpoint;
(f) evaluating the at least one design change resulting from the optimization procedure to determine the net cost and benefit of the change;
(g) comparing the net cost and benefit of the optimization procedure just performed with the net cost and benefit of the previous optimization procedure performed associated with the previous retained checkpoint, and retaining the best net cost and benefit and final checkpoint of the optimization procedure just performed if there is an improved net cost and benefit;
(h) returning the design model to the immediately previous retained checkpoint;
(i) repeating steps (e) to (h) a predetermined number of times; and
(j) returning the design model to its state at the checkpoint of the optimization procedure that has resulted in the last net cost and benefit retained or to its state at the initial checkpoint in the event that no optimization procedure improved the design model so that the design is optimally changed to a new design.